#include"HuffmanTree.h"
#include<iostream>
#include<queue>
#include<unordered_map>
#include<string>
#include<memory>
#include<vector>
#include<fstream>
#include<assert.h>
#include<stack>
#include<unordered_set>
using namespace std;
namespace dzh
{
	//小堆的比较用仿函数（小堆用大于）
	struct Compare
	{
		bool operator()(pair<char, int> a, pair<char, int> b)
		{
			return a.second > b.second; 
		}
	};
	struct HuffmanNode
	{
		HuffmanNode(int weight, char data, int left = -1, int right = -1, int parent = -1)
			:_weight(weight)
			,_left(left)
			,_right(right)
			,_parent(parent)
			,_data(data)
		{
		}
		int _weight = -1;
		int _left = -1;
		int _right = -1;
		int _parent = -1;
		char _data = ' ';
	};
	ostream& operator<<(ostream& os, const HuffmanNode& t)
	{
		os << "权重：" << t._weight << " 左孩子：" << t._left << " 右孩子：" << t._right << " 父母：" << t._parent << " 字符：" << t._data << endl;
		return os;
	}
//	//编码表用类：vector存储时需要，本程序打算直接使用哈希进行编码表的存储
//	struct CodeTable
//	{
//		CodeTable()
//		{
//		}
//		char _ch = ' ';
//		string code;
//	};
	class HuffmanTree
	{
	public:
		HuffmanTree(string filename)
			:_filename(filename)
		{
			unordered_map<char, int> m;
	//		ofstream ofs(filename);
			ifstream ifs(filename, ios_base::binary | ios_base::in);
			//读取文件，并使用哈希计算每个字符出现的次数
			if(ifs.is_open())
			{
				char c = ' ';
				while (ifs.read(reinterpret_cast<char*>(&c), 1))
				{
					++_sourceCharCount;
					++m[c];
				}
			}
			else
			{
				assert(false);
			}
			ifs.close();

			//注意判断一下文件中没有数据的情况，直接停止程序
			if(m.empty())
			{
				cout << "文件中没有数据！" << endl;
				assert(false);
			}
			_uniqueCharCount = m.size();//将哈希中的size赋值给_uniqueCharCount

			//将哈希中的数据入小堆
			priority_queue<pair<char, int>, vector<pair<char, int>>, Compare> q;
			for(const auto& e : m)
			{
				q.emplace(e);
			}
			//将小堆中的数据依次存放入vector，即创建仿二叉树
			//此过程共分为两步，第一步是将创建的所有节点全部放入vector
			//第二步是为vector中的每个节点找到对应的parentnode
			
			//第一步
			_root = make_unique<vector<HuffmanNode>>();
			while(q.size() > 1)//当堆中数据个数为1时，说明树已经创建完毕了
			{
			//	cout << q.size() << endl;
				HuffmanNode n1(q.top().second, q.top().first);
				q.pop();
				HuffmanNode n2(q.top().second, q.top().first);
				q.pop();
				pair<char, int> parentnode(' ', n1._weight + n2._weight);
				q.emplace(parentnode);
				_root->emplace_back(n1);
				_root->emplace_back(n2);
			}
			assert(!q.empty());
			_root->emplace_back(q.top().second, q.top().first);//将堆中剩下的根节点放到vector中
			q.pop();

			//第二步
			//由于上面使用优先级队列进行vector的插入，所以，现在vector中的数据应是根据weight的值进行从小到大排列的，因此，现在仅需要每次循环都依次访问两个数据
			for(size_t i = 0; _root->size() != 0 && i < _root->size() - 1; i += 2)//最先要注意的就是size==0的问题，由于返回值是size_t，所以要极力避免size == 0 && size - 1的情况
			{
				for(size_t j = i + 2; j < _root->size(); ++j)//由于vector是按照从小到大的顺序排列的，所以直接从i+2的位置开始搜索权重合适且data为空的节点
				{
					if((*_root)[j]._weight == (*_root)[i]._weight + (*_root)[i + 1]._weight && (*_root)[j]._data == ' ' && (*_root)[j]._left == -1 && (*_root)[j]._right == -1)
					{
						(*_root)[i]._parent = j;
						(*_root)[i + 1]._parent = j;
						(*_root)[j]._left = i;
						(*_root)[j]._right = i + 1;
						break;
					}
				}
			}

			//建好模拟树后，开始建立编码表与反编码表
			_table = make_unique<unordered_map<char, string>>();
			_table->reserve(_uniqueCharCount * 4 / 3);//利用_uniqueCharCount提前扩充好哈希表（注意，一般负载因子是0.75，所以这里使用负载因子的倒数），避免后续可能的多次扩充造成的资源浪费
			_retable = make_unique<unordered_map<string, char>>();
			_retable->reserve(_uniqueCharCount * 4 / 3);
			string codes = "";
			stack<char> sk;
			char mid = '0';
			//assert(_root->empty());
			for(size_t i = 0; i < _root->size(); ++i)
			{
				const auto& e = (*_root)[i];
				//cout << e._data << endl;
				if(e._data != ' ')
				{
					//cout << 1 << endl;
					int child = i;
					int parent = e._parent;
					while(parent != -1)
					{
						if(&(*_root)[(*_root)[parent]._left] == &(*_root)[child])//使用地址进行左右节点的比较，先开始使用的data进行比较，但因为中间节点的data均为' ',会导致无法正确区分，想到了可以直接使用地址进行比较
						{
							mid = '0';
						}
						else
						{
							mid = '1';
						}
				//		cout << mid << endl;
						sk.emplace(mid);
						child = parent;
						parent = (*_root)[parent]._parent;
					}
					while(!sk.empty())
					{
						codes += sk.top();
					//	cout << sk.top();
						sk.pop();
					}
					//cout << codes << endl;
					_table->emplace(e._data, codes);
					_retable->emplace(codes, e._data);
					codes = "";
				}
			}
		}
		//使用文本形式写入01，是压缩的中间实验函数
		//void EnCode(string codeFileName)
		//{
		//	ifstream ifs(_filename, ios_base::in);
		//	ofstream ofs(codeFileName, ios_base::out);
		//	char ch = ' ';
		//	string s = "";
		//	while(ifs >> ch)
		//	{
		//		s = (*_table)[ch];
		//		ofs << s;
		//	}
		//	ofs.close();
		//	ifs.close();
		//}

		//使用二进制形式写入01，是最终的结果函数
		void EnCode(string codeFileName)
		{
			//一个源文件可能需要被压缩成多份，因此使用哈希存储压缩文件的文件名，方便解压时判断文件是否是被该类压缩的
			_codeFileName.emplace(codeFileName);
			ifstream ifs(_filename, ios_base::binary | ios_base::in);
			ofstream ofs(codeFileName, ios_base::binary | ios_base::out);
			char ch = ' ';//用于读取源文件中的字符
			unsigned char buf = 0;//用于记录二进制位
			string s = "";
			int count = 7;//用于记录当前char未被使用的比特位数（范围为0~7）
			while (ifs.read(reinterpret_cast<char*>(&ch), 1))
			{
				s = (*_table)[ch];
				for(const auto& e : s)
				{
					size_t bitValue = e - '0';
					buf |= (bitValue << count);
					--count;
					if(count == -1)
					{
						ofs.write(reinterpret_cast<const char*>(&buf), 1);
						buf = 0;
						count = 7;
					}
				}
			}

			//记得处理最后存储在buf中但比特位还未使用完全的数据
			if(count != 7)
			{
				ofs.write(reinterpret_cast<const char*>(&buf), 1);
			}
			ofs.close();
			ifs.close();
			cout << "压缩成功！" << endl;
		}
		void DeCode(string codeFileName, string deCodeFileName)
		{
			if(_codeFileName.find(codeFileName) == _codeFileName.end())
			{
				cout << "所解压的文件不是由当前对象压缩的！" << endl;
				return;
			}
			ifstream ifs(codeFileName, ios_base::binary | ios_base::in);
			assert(ifs.is_open());
			ofstream ofs(deCodeFileName, ios_base::out);
			char ch = ' ';//用于将转码后的字符写入文件
			unsigned char buf = 0;//用于记录二进制位
			string decodedOutput = "";//用于读取二进制中的比特位
			int count = 7;//用于记录当前已经读取完毕的比特位（范围为0~7）
			size_t num = 0;//记录成功转换的字符个数，与压缩时的总字数对比，相等则停止转换
			while (ifs.read(reinterpret_cast<char*>(&buf), 1))
			{
				while(count > -1)
				{
					if(num == _sourceCharCount)//读取到最后一个字节，可能出现bit中遇到填充用的二进制的0的情况，此时仅需break内部循环即可，因为此时已是最后一次外部循环
					{
						break;
					}
					char binNum = ((buf >> count) & 1) + '0';//这里一定注意运算符优先级问题，要把1放到小括号中，先与&运算，再+
					--count;
					decodedOutput += binNum;
					if(_retable->find(decodedOutput) != _retable->end())
					{
						ch = (*_retable)[decodedOutput];
			//			cout << ch << " ";
						ofs << ch;
						ch = ' ';
						decodedOutput = "";
						++num;
					}
				}
				count = 7;
			}
			if(ifs.eof())
			{
				cout << "文件解压成功！" << endl;
			}
			else if(ifs.fail())
			{
				cout << "文件解压失败！" << endl;
			}
			else if(ifs.bad())
			{
				cout << "ifstream出现系统级错误！" << endl;
			}
			else
			{
				assert(false);
			}
		}
		void PrintTree()
		{
			for(const auto& e : *_root)
			{
				cout << e << endl;
			}
		}
		void PrintTable()
		{
			for(const auto& e : *_table)
			{
				cout << "字符为：" << e.first  << " 编码为：" << e.second << endl;
			}
		}
		size_t UniqueCharCount()
		{
			return _uniqueCharCount;
		}
		size_t SourceCharCount()
		{
			return _sourceCharCount;
		}
	private:
		unique_ptr<vector<HuffmanNode>> _root = nullptr;
		unique_ptr<unordered_map<char, string>> _table = nullptr;
		unique_ptr<unordered_map<string, char>> _retable = nullptr;
		size_t _uniqueCharCount = 0;
		size_t _sourceCharCount = 0;
		string _filename = "";
		unordered_set<string> _codeFileName;
	};

	void test1()
	{
		cout << "请输入源文件的文件名：" << endl;
		string fileName;
		cin >> fileName;
		HuffmanTree ht(fileName);
		cout << "总字符数为：" << ht.SourceCharCount() << endl;
		cout << "HuffmanTree为：" << endl;
		ht.PrintTree();
		cout << "编码表为：" << endl;
		ht.PrintTable();
		cout << "请输入压缩文件的文件名：" << endl;
		string codeFileName;
		cin >> codeFileName;
		ht.EnCode(codeFileName);
		cout << "请输入需要解压的文件的文件名以及接收解压后文件的文件名：" << endl;
		string deCodeFileName;
		cin >> codeFileName >> deCodeFileName;
		ht.DeCode(codeFileName, deCodeFileName);
	}
	void test2()
	{
		HuffmanTree ht("HuffmanTree_test.txt");
		string codeFileName;
		ht.PrintTable();
		ht.PrintTree();
		ht.EnCode("zip.txt");
		ht.DeCode("zip.txt", "yuanwenjian.txt");
	}
}
